using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

// 四叉树-区域节点
[Serializable]
public class Node
{
    /// <summary>
    /// 深度
    /// </summary>
    public int level;
    
    /// <summary>
    /// leftdown
    /// </summary>
    public Vector3 minP;
    
    /// <summary>
    /// rightup
    /// </summary>
    public Vector3 maxP;

    public Vector3 center;
    
    /// <summary>
    /// 下层节点
    /// </summary>
    public Node leftup;
    public Node rightup;
    public Node leftdown;
    public Node rightdown;

    public List<Vector3> points;

    public Node(Vector3 minPos, Vector3 maxPos)
    {
        minP = minPos;
        maxP = maxPos;
        center = (maxP + minP) / 2;
        points = new List<Vector3>();
    }

    /// <summary>
    /// 深入下一节点
    /// </summary>
    public void Grow()
    {
        if (points == null || points.Count <= 4)
            return;
        
        Vector3 midup = new Vector3(center.x, maxP.y, 0);
        Vector3 midright = new Vector3(maxP.x, center.y, 0);
        Vector3 middown = new Vector3(center.x, minP.y, 0);
        Vector3 midleft = new Vector3(minP.x, center.y, 0);
        
        leftup = new Node(midleft, midup);
        leftup.level = level + 1;
        rightup = new Node(center, maxP);
        rightup.level = level + 1;
        leftdown = new Node(minP, center);
        leftdown.level = level + 1;
        rightdown = new Node(middown, midright);
        rightdown.level = level + 1;
        
        for (int i = 0; i < points.Count; i++)
        {
            var p = points[i];
            if (leftup.isContainer(p))
            {
                leftup.points.Add(p);
            }
            else if (rightup.isContainer(p))
            {
                rightup.points.Add(p);
            }
            else if (leftdown.isContainer(p))
            {
                leftdown.points.Add(p);
            }
            else if (rightdown.isContainer(p))
            {
                rightdown.points.Add(p);
            }
            else
            {
                Debug.LogError("[Node] output range: " + p);
            }
        }

        points.Clear();
    }

    /// <summary>
    /// 是否包含点在内
    /// </summary>
    /// <param name="p"></param>
    /// <returns></returns>
    public bool isContainer(Vector3 p)
    {
        return (p.x <= maxP.x && p.y <= maxP.y && p.x > minP.x && p.y > minP.y);
    }

    /// <summary>
    /// 测试区域检测判定
    /// </summary>
    /// <param name="sPos"></param>
    /// <param name="ePos"></param>
    /// <returns></returns>
    public bool isThrough(Vector3 sPos, Vector3 ePos)
    {
        bool result = false;
        if (sPos.x == ePos.x)
        {
            float maxY = Math.Max(sPos.y, ePos.y);
            float minY = maxY == sPos.y ? ePos.y : sPos.y;
            result = (sPos.x >= minP.x && sPos.x <= maxP.x && minP.y > minY && maxP.y < maxY);   // verticel
        }
        else
        {
            float maxX = Math.Max(sPos.x, ePos.x);
            float minX = maxX == sPos.x ? ePos.x : sPos.x;
            result = (sPos.y >= minP.y && sPos.y <= maxP.y && minP.x > minX && maxP.x < maxX);   // horizontal            
        }
        
        return result;
    }

    /// <summary>
    /// 通过 pos 递归查找最深 child node
    /// </summary>
    /// <param name="pos"></param>
    public List<Node> Output(Vector3 ld, Vector3 rt, Vector3 lt, Vector3 rd)
    {
        List<Node> result = new List<Node>();

        if (leftdown != null)
        {
            leftdown.Output(ld, rt, lt, rd).ForEach(n =>
            {
                result.Add(n);
            });
        }
        
        if (rightdown != null)
        {
            rightdown.Output(ld, rt, lt, rd).ForEach(n =>
            {
                result.Add(n);
            });
        }
        
        if (leftup != null)
        {
            leftup.Output(ld, rt, lt, rd).ForEach(n =>
            {
                result.Add(n);
            });
        }
        
        if (rightup != null)
        {
            rightup.Output(ld, rt, lt, rd).ForEach(n =>
            {
                result.Add(n);
            });
        }

        bool container = isContainer(ld) ||
                         isContainer(rt) ||
                         isContainer(lt) ||
                         isContainer(rd) ||
                         isThrough(ld, rd) ||
                         isThrough(ld, lt) ||
                         isThrough(lt, rt) ||
                         isThrough(rt, rd);
        if (result.Count <= 0 && container)
            result.Add(this);
        
        return result;
    }
}
